package com.kuang.array;

/*
*   给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
    子数组是数组中的一个连续部分。
* */


import java.util.Arrays;

/**
 * @author kjx
 */
public class MaxSubArray {

    //第一种方法就是用上一题刚刚做的寻找子数组和为k的子数组一样的方法
    //用前缀和做,问题转换为找到前缀和数组中后面的减去前面的最大值（前面的不能大于零）
    public static int maxSubArray(int[] nums) {
        if (nums.length <= 1) return nums[0];
        int pre = nums[0], maxPre = pre, minPre = pre, result = pre; //定义最大前缀和和最小前缀和
        for (int i = 1; i < nums.length; i++) {
            pre += nums[i];
            maxPre = minPre < 0 ? pre - minPre : Math.max(pre, maxPre);
            result = Math.max(result, maxPre);
            minPre = Math.min(minPre, pre);
        }
        return result;
    }



    //前缀和的修改版本,简化代码
    public static int maxSubArray2(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int minPreSum = 0;
        int preSum = 0;

        for (int x : nums) {
            preSum += x;  // 当前的前缀和
            ans = Math.max(ans, preSum - minPreSum);  // 减去前缀和的最小值
            minPreSum = Math.min(minPreSum, preSum);  // 维护前缀和的最小值
        }

        return ans;
    }



    //这里给出官方第一种动态规划的思想解法，看似很简单，但是不好理解！！！
    public static int maxSubArray3(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }


    public static void main(String[] args) {
        int[] testArr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray2(testArr));
    }
}
